Khái niệm NP-đầy đủ được đưa ra bởi Stephen Cook năm 1971 trong bài báo mang tên "The complexity of theorem-proving procedures".[1] Tuy nhiên tên gọi NP-đầy đủ không xuất hiện trong bài báo này mà được đưa ra sau này. Trong đó Cook đã chứng minh định lý Cook-Levin (Leonid Levin cũng chứng minh định lý này một cách độc lập cùng thời gian với Cook). Định lý này chứng minh bài toán Circuit-SAT là NP-đầy đủ. Năm 1972, Richard Karp chứng minh 21 bài toán khác cũng là NP-đầy đủ.[2]. Từ sau đó đến nay, hàng nghìn bài toán đã được chứng minh là NP-đầy đủ. Nhiều bài toán quan trọng trong số đó được liệt kê trong cuốn "Computers and Intractability: A Guide to the Theory of NP-Completeness" của Garey và Johnson.[3]